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

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

Alan Szepieniec holds a PhD in post-quantum cryptography from KU Leuven. His research is focused on cryptography, particularly the type of cryptography that is helpful for Bitcoin.

Proof-of-stake is a proposed alternative consensus mechanism to the proof-of-work that Bitcoin’s consensus mechanism uses. Proof-of-stake does not require the consumption of energy. Instead, miners (also known as validators) must place digital assets at stake to participate in the block production process. To avoid losing their stake, they are incentivised to act honestly by staking. The theory is that the network can quickly reach consensus with only honest validators about the order of transactions, and therefore about which double-spends are valid.

Proof-of-stake has been the subject of much debate. Most criticisms center on security. Does it reduce the cost of attacks? Many people also raise sociological concerns, such as centralization of power, wealth concentration, plutocracy, and others.

In this article, I make a more fundamental criticism of proof-of-stake: It is subjective. Depending on who you ask, the correct view of a proof -of-stake Blockchain depends on what they are looking at. The cost of an attack cannot therefore be calculated in units within the blockchain. Security analyses are null. Debts cannot be settled between parties who do not agree on the credibility of third parties. Courts must resolve disputes.

Proof-of-work, on the other hand, is an objective consensus mechanism that allows any group of related or unrelated parties to agree on the correct state of the blockchain. In other words, any two economic actors can decide whether a payment was made. This is independent of courts and influential community members. This distinction makes proof of work and proof-of stake both suitable 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 allows computers to create exact copies of the original copy without any cost. Computers can copy almost anything as long as it’s digital.

However, there are some things that exist purely in the digital realm that can’t be copied. Things that are both scarce and digital. This applies to bitcoin, for example, and other blockchain-based digital assets. They can be sent but the original copy must be returned. Although one might disagree with the reasons for these assets being needed, the fact that they exist means that these digital assets can be used as an alternative to balance exchanges. They are money, condensed to one word.

The blockchain protocol replicates a ledger over a network to achieve digital scarcity. The ledger can only be updated if the owners of the spent money agree to it; the net sum is zero and the outputs are positive.

Any invalid update will be rejected. Digital scarcity can only be guaranteed if there is consensus among all protocol participants about the ledger’s state.

It turns out that it is difficult to achieve consensus. Incorrect network conditions can lead to different views of history. Sometimes packets are lost or delivered in an incorrect order. Networks are prone to disagreement.

The Fork-Choice Rule

Blockchains address this problem in two ways. They enforce a complete order on all transactions which creates a tree of alternate views of history. They also define canon for histories and a fork-choice rules that determines the canonical branch of the tree of history. It is possible to deduce canonicity from trusted authorities, or, according to some people, from a digital voter registration scheme that is backed up by a citizen identification 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. Both solutions assume that third parties are trustworthy and can be trusted. We want to reduce trust assumptions. Ideally, we have a solution that is entirely mathematical.

A solution to canonicity that is entirely mathematical generates the amazing property that the answer is independent of who computes it. This is the only way a consensus mechanism can be objective. One caveat is that it is essential to assume that all parties agree upon a single reference point such as the genesis block and its hash digest. A consensus mechanism that allows any party to extrapolate from this reference point the canonical view is called an objective consensus mechanism.

It doesn’t matter which branch of the tree is chosen to be canonical. What is important is that all parties can agree on this decision. The whole tree does not have to be represented on one computer. It is sufficient for each node to have a few branches. The fork-choice rule can only test two candidate views of history at a time. The phrase “the canonical view” is misleading. A view of history cannot be more or less canonical relative other views. Nodes propagate the branch that is more canonical by dropping the branch that is less canonical. A new view of history is more canonical when it is extended with a bunch of transactions.

The fork-choice rule must have two properties in order to allow the network to quickly reach consensus on the canonical view. It must be clear and efficient for all views of history. It must be transitive for all triple views of history. For those who are mathematically inclined, let U,V and W be any three views of historical events. The infix “” will denote the fork choice rule favoring the left-hand side over that of the right. Then: either

  • U

or

  • V
  • U

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. Two additional properties are needed. When comparing two views, one must be considered as an extension of the other. The fork-choice rule must always favor extended views. Second, extensions to a (previously) canonical view are more likely than extensions to non-canonical views. Then:

  • U
  • U12

The last property incentivizes honest extenders to focus on extending canonical views as opposed to views that they know are not canonical. Because of this incentive, divergent views of history that result from honest, but contradictory extensions tend to differ only in the tips of recent events. The further back an event is recorded, the less likely it is to be overturned by a reorganization that is more canonical. This perspective allows us to define the limit of historical views that the network can converge.

The obvious disqualifier in paragraph 1 is the requirement that extenders behave honestly. What about dishonest extenders. If the adversary can control a random variable implicitly in the probability expression, he can engineer it to advantage and launch deep organizational reorganizations with high success probabilities. Even if the adversary cannot control the random variables, but can produce candidate extensions cheaply, then the fork-choice rules can be evaluated locally and indefinitely until the opponent finds an early-on point or divergence. This can also allow him to find an extension that generates a more canonical branch that any other that circulates.

The missing piece of this puzzle is not a mechanism to prevent dishonest extensions. It is impossible to distinguish dishonest behavior in an environment with imperfect network conditions. An attacker can ignore messages that aren’t to his liking or delay their propagation, and claim that the network is to blame. The missing piece of this puzzle is a mechanism which makes deep reorganizations more costly than shallow ones and more expensive as they go.

Cumulative Proof-Of-Work

Satoshi Nakamoto’s consensus mechanism achieves precisely this. To propose a new set of transactions (called blocks) and thus extend some branch, would be extenders (called miner) must first solve a mathematical puzzle. This puzzle is difficult to solve, but it is easy to verify. It is therefore appropriately named proof-of work. Only the solution to this puzzle (and the history it commits) can make the puzzle a valid contender to be made canon. The puzzle has a knob that adjusts its difficulty. This knob is turned to set a regular time until a new solution is found. It does not matter how many people are involved or how much they spend on the problem. This knob serves a secondary purpose as an impartial indicator of puzzle-solving effort in a unit measuring difficulty.

Anyone can participate in this process. The limiting factor in the process is not authority, cryptographic key material, or hardware requirements. Rather, it is the amount of resources one is willing and able to spend 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), it is simple to calculate an objective estimate of how much work a given branch represents. The branch with a higher proof-of-work, fork choice rule is preferred.

Miners race against each other to find the next block. The first miner who successfully propagates it and finds it wins. Assuming miners don’t have valid, unpropagated blocks, they will accept a new block from other miners. Failure to do so will put them at a disadvantage. It is unreasonable to build on top of an old block because it is impossible to catch up with the rest and find two new blocks to succeed. This task is twice as difficult as switching to a longer branch and then extending it. Reorganizations in a proof-of work blockchain tend to be isolated to the tip. This is not because miners are lying, but because the cost to generate reorganizations increases with the depth. 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. Validators sign new blocks. Participating nodes verify the signatures on the blocks to confirm that the view of history is correct.

The node does not have the ability to distinguish valid views from invalid. A competing block can only be considered a serious contender for the tip with a supporting signature (or multiple supporting signatures). Because of their malicious behavior, validators will not sign alternative blocks. This would result in their stake being lost.

The process is open to all. Anybody can become a validator by depositing a certain amount in an escrow account. This escrowed money is the “stake” which is cut if the validator is not being responsible. Nodes verify that signatures on new blocks match those of validators who put their stakes in escrow.

Formally, in proof-of-stake blockchains, the definition of the correct view of history is entirely recursive. Only valid new blocks can be created if they have the correct signatures. Signatures are valid in relation to the public keys of validators. These public keys are determined using old blocks. Fork-choice rules are not applicable to competing views of history as long as both views are consistent.

In the opposite, the correct view for history in proof-of work blockchains can also be defined recursively but not to exclude external inputs. In particular, the fork-choice rule of proof-of-work relies on randomness whose objective verifiability is also verifiable.

This external input is the main difference. Proof-of-work defines the fork-choice rules for any pair of competing views of history. This is why it’s possible to talk about canon. Proof-of-stake can only define correctness relative a prior history.

Proof-Of-Stake Is Subvertible

Does it matter though? It is theoretically possible to produce two consistent, but mutually incompatible views on history if someone has been dishonest. If they have, it is possible for them to prove their dishonesty and reduce their stake. It is possible to recover from the point of divergence where the validator is not in dispute.

The problem with this argument, however, is that it doesn’t take into account time. If a validator signed mutually contradicting blocks ten years ago, that is, published a new contradictory counterpart to the block that had been confirmed ten year ago, then the history of the block will have to be rewritten. The stake of the malicious validator is reduced. Transactions that use the staking rewards will be invalid. If given enough time, the validator may see his rewards percolate to a large portion of the blockchain economy. The recipient of coins cannot guarantee that all dependencies will be valid in the future. Because it is easier and less expensive to reorganize the distant past than the present, there is no finality.

Proof-Of-Stake Is Subjective

The only way to solve this problem is to restrict the depth at which reorganizations are admitted. Contrasting views of history that diverge at the first point are not allowed. Nodes presented with a different view that has a earlier point of divergence should reject it without testing which one is correct. Continuity is guaranteed as long as there are nodes that are active at any given moment. If there are too many reorganizations, the blockchain cannot evolve.

This solution makes proof-of stake a subjective consensus mechanism. The answer to the question, “What is the current state? of the blockchain?” will depend on who you ask. It is not objectively verifyable. An attacker could present a different view of history that is as consistent as the correct one. A node cannot determine which view is correct unless it selects a group of peers and accepts their word for it.

It may be argued this hypothetical attack is irrelevant if it is too expensive to produce an alternative view of history. Although this counterargument may be true, it is not objective and costs are an objective metric. Therefore, whether or not it is true will depend on external factors that aren’t represented on the blockchain. The attacker may lose all his stake in one view, but he doesn’t care, as he can guarantee that the other view will be accepted through legal and social means. 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. If the attacker uses his attack, it is not because the payout is determined mechanically by his ingenuity. Instead, the official team of developers broadcasts the reason they chose the other branch. External payouts may exist, such as financial options that expect the price will fall or the sheer joy of causing mayhem. However, the argument that an attack bounty is based on the market capitalization for existing proof-of-stake cryptocurrency markets is weakening because of the low likelihood of receiving internal payouts.

Money And Objectivity

Money is, in essence, the object with which a debt is settled. To settle debt effectively, there must be consensus among all parties to the exchange — mainly the currency and the amount. A dispute can lead to the perpetuation and refusal to do business again on similar terms or with equal claims.

Effective debt settlement does not require the entire world to agree on the specific type of money. A subjective money can be used in areas of the world economy that have reached consensus. Global consensus is necessary to bridge the gap between micro-economies or between people around the world. A consensus mechanism that is objective achieves this; a subjective one doesn’t.

Proof-of-stake cryptocurrencies cannot provide a new foundation for the world’s financial backbone. The world is made up of countries that don’t recognize each other’s courts. War is the only recourse if there is a dispute about the correct view on history.

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 if a cryptocurrency exchange allows a large withdrawal downstream of a deposit in a proof of-stake cryptocurrency whose transaction appears only in one branch of two competing views? The exchange may choose the view that is most profitable for them, but if the community, prompted by the PGP signatures, tweets and Medium posts from developers, foundations, and influencers, chooses to see the other view, the exchange will be responsible. They have every incentive to recover their losses from those responsible. In the end, a court will decide which view of history is correct.

Conclusion

Proponents of proof-of-stake claim that it serves the same purpose as proof-of-work, but without all the energy waste. Their support often ignores the tradeoffs inherent in engineering dilemmas. Although proof-of-stake eliminates energy expenditure, it also compromises the objectivity and credibility of the resulting consensus mechanism. This is fine in situations where only a small amount of consensus is needed, but it raises the question: What good is it to eliminate the trusted authority? An objective mechanism is required to ensure a global financial backbone.

The self-referential nature proof-of-stake is subjective. Which view of history you choose depends on who you ask. The question “Is proof-of-stake secure?” aims to reduce the analysis to an objective measurement of cost that does not exist. The popularity of the fork among influential members of the community will determine which fork is correct in the short-term. Courts will have the power to decide which fork is correct in the long-term. The borders that define the boundaries between the jurisdictions of one court and the beginning of another will be influenced by the local consensus.

The energy used by miners to create proof-of-work blockchains does not go to waste, just like diesel is used to fuel cars. It is used to exchange cryptographically verifiable and unbiasable randomness. Without this key ingredient, we don’t know how to create an objective consensus mechanism.

This is a guest post by Alan Szepieniec. Opinions expressed do not necessarily reflect those held by BTC Inc. or Bitcoin Magazine ..

Read More