Blockchain Consensus Protocols & Game Theory

0
50

The purpose of this writing is to analyze the game theory behind the two most prominent consensus protocols in blockchain — Proof of Work and Proof of Stake. The first section is meant to give beginners a better understanding of blockchain technology and game theory before inspecting the game theory for each protocol and their defense against attacks. It may take time to unpack the information for those unfamiliar with blockchain technology, but the paper doesn’t dive into all the complex details that experts have covered in other analyses.

Furthermore, this research doesn’t cover the game theory of blockchain outside the consensus protocol such as the adoption by private and public entities. The goal is not to evaluate the effectiveness of different blockchains beyond consensus protocols, nor does it provide analysis on the various economic factors related to blockchain, such as supply flow, supply cap, utility, etc. Most importantly, nothing in this paper is investment advice.

By looking closely at the perspective of players involved in blockchain consensus, the payoffs for each player, and the game theoretical approaches to different strategies, one is able to better understand why blockchains are considered secure despite being decentralized and trustless.

BLOCKCHAIN BASICS

“At a high level, blockchain technology allows a network of computers to agree at regular intervals on the true state of a distributed ledger,” says MIT Sloan assistant professor Christian Catalini, an expert in blockchain technologies and cryptocurrency (Church 2017). Blockchain is solving a difficult problem by aligning the network to one ledger without any trust required and allowing each computer to store the true ledger. Distributing the ledger is the critical step that opens the door to decentralizing finance, voting, supply chain, and many other systems that are currently controlled by centralized entities.

One way to better understand blockchains and distributed ledgers is to look at their opposite — centralized ledgers. A good example of a centralized ledger is a bank. A bank holds all the balances and tracks the transactions of it’s accounts on a centralized ledger. Just like individuals track their total wealth and the flow of money in and out of their own personal checking accounts, banks do this for all of their customers’ accounts. By relying on the bank to control this aspect of their lives, people are trusting them to properly store their wealth and manage the movement of their money throughout the broader financial system.

Decentralization removes the central authority and puts the power into the members of the network. From a financial perspective, it is equivalent to removing the bank and allowing people to hold and track their personal wealth and openly transact with others in the network without any censorship from an outside authority. Before digging into how decentralization is possible through blockchains, it’s important to weigh the pros and cons of decentralization.

There are three areas to weigh tradeoffs: security, economics, and censorship. From a security perspective, decentralization removes a single point of attack. This is a great characteristic for storing wealth or important information, but it does require energy or complex algorithms (or both) to maintain. If people feel better trusting their wealth with banks or other entities that invest heavily in security, then decentralization is less necessary for those people.

Regarding economics, decentralization can help when central authorities are charging high fees or are known to be corrupt or short sighted. Take for example a company that has a stranglehold over the transfer of wealth across borders — possibly for remittances. If competition is weak in this sector, fees may be high and creating a path around the central authority could reduce fees.

Another example is a government that has historically acted against the wishes of its constituents and/or been untrustworthy with the supply of money resulting in excessive inflation. Instead of continuing to store money in that government’s currency, a person could store their wealth on a decentralized blockchain that may be less prone to manipulation by a single party. On the other hand, what if competition is strong and the government has historically acted honestly and effectively? Maybe decentralization is just a distraction for the economy. People in a decentralized world have more personal responsibility and have to spend more time focused on storing their wealth, rather than spending that time contributing to the economy. Admittedly, hyperinflation can cause this same outcome because people are constantly searching for new ways to store their wealth as inflation ruins the value of their cash.

The final characteristic of decentralization up for debate is censorship resistance. By removing a central authority, transactions or the information stored on the blockchain can’t be censored. The general goal is to allow peer to peer transactions free of a government’s or business’s influence. That seems like a strong pro for decentralization, but what about when people want help from a third party when they make a mistake? If a person loses their credit card, another person may use the card to buy candy at several gas stations. Banks will find a way to pay the credit card owner back for their lost money. In a decentralized world, that money is gone.

Decentralization and distribution of the ledger in blockchains have several pros and cons, but the principle and technology are likely to be an important part of the future. Now, how can decentralization actually be achieved? The problem of aligning participants to the true state of the ledger without requiring trust between the participants is extremely difficult. Mathematicians, computer scientists, and game theory experts have been working on this problem for over fifty years.

The developments of cryptography and digital money over the years eventually led to the creation of consensus protocols that help secure and maintain the blockchains that are popular today. As the timeline below portrays, one of the first consensus protocols is called Proof of Work and was created by Adam Back in 2002. Later, Proof of Stake came to life with Peercoin and became more popular with blockchains like Cardano and several others. One of the most significant changes in the space of consensus protocols is the move of Ethereum from Proof of Work to Proof of Stake that is currently in progress as of September 2021.

Although this analysis doesn’t dig deeper into the history of work from leaders in this space, there are several resources online that show the depth of research and experimentation that were involved in the eventual creation of blockchains in 2009. Also, a common theoretical problem used to understand the struggles and solutions of decentralization is called the Byzantine Generals problem. In Appendix Item A, the Byzantine Generals problem is explained and a game theoretical analysis is applied.

GAME THEORY BASICS

In preparation for the analysis in subsequent sections, the next step is to describe the basics of Game Theory. Game Theory is the study of strategic interactions between players. Every game involves three elements — players, strategies, and payoffs. Examples of payoffs could be winning or losing, earning more money or less money, or time in jail.

Arguably the most critical aspect of the game is that the payoffs rely on the actions of the other player. The most common way to analyze the payoffs of a game is to use a payoff matrix that shows the payoffs for each player when each player chooses different strategies. The players are able to decide their optimal strategies based on the actions of their opponent. When both players’ optimal strategies align, there is a Nash equilibrium — each player has nothing to gain from changing their strategy.

Interestingly, the Nash equilibrium doesn’t need to be the best outcome for each player but the best outcome based on the optimal strategy for their opponent. A good example of this scenario is explained by the Prisoner’s Dilemma. Harry and Sally are locked up for a crime. They are offered a deal if they confess and testify against their partner in crime. If Harry and Sally both stay silent, they get one year in jail. If one confesses and the other doesn’t, the confessing player gets to go free and the other gets five years. If they both testify against each other they each get three years.

The above table is a “payoff matrix” for the game between Harry and Sally. Each player isn’t able to coordinate or talk to each other so they have to analyze based on the payoffs for themselves and their opponents.

Sally deciding based on Harry’s two options.
Harry deciding based on Sally’s two options.

On the left, Sally is looking at Harry’s strategies to be silent or to testify. If Harry is Silent, her optimal strategy is to testify so she doesn’t spend any time in jail. If Harry testifies against her, the optimal strategy is to again testify against Harry to get three years instead of five years. On the right side, Harry comes to the same conclusions based on Sally’s choice between silence and testifying.

Now the Nash equilibrium is clear. Both Harry and Sally will testify and each get three years. It wasn’t their best outcome, but it was the optimal strategy based on the actions of the other player. Often, there are external forces attempting to bring each player to their best outcome. For Harry and Sally, that could mean an outside force like a group of other criminals that will punish Harry and Sally for testifying against a fellow criminal. For competition between companies, that might look like collusion or price fixing.

Another game theoretical approach is called the Maximin strategy when a player is attempting to choose the strategy that optimizes the worst case scenario. If they aren’t trying to maximize the greatest payoffs and would rather maximize the lowest payoff, they can take this strategy. For Harry and Sally, the Maximin is also to testify because they want to eliminate the risk of going to jail for five years.

When these two game theoretical approaches aren’t sufficient, the game can be analyzed using mixed strategies and looking deeper at what each player has to believe about the other player to take a certain action. The paper will dig into this further when looking at the players within blockchains. There are several other game theoretical approaches, but this paper will focus on these three: Nash Equilibrium, Maximin Strategy, and Mixed Strategies.

GAME THEORY & BLOCKCHAIN CONSENSUS

How does game theory apply to blockchains? For this analysis, the focus will be on the game theory behind the different participants coming to consensus on the true state of the ledger. The players that this paper will analyze are the miners in Proof of Work and validators in Proof of Stake that secure the blockchain and provide consensus.

In order to reduce complexity of the analysis, the payoffs will be simplified ranging from -1 to 2. -1 will represent the worst outcome, 0 will be breakeven, 1 will be positive but not optimal, and 2 will be the optimal payoff. The games will weigh the payoffs when players are honest and continuing to secure the network against the payoffs when the players are dishonest and attacking the network. Every blockchain is built with incentives or rewards for being honest such as newly created coins and/or transaction fees provided to the honest players. The risk in blockchain consensus becomes severe when participants are able to take over the majority of the network and manipulate the ordering of events. When this occurs, it is called a 51% attack.

During a 51% attack, the attacking player(s) is/are able to change the ordering of transactions that they initiated. The most common type of manipulation during an attack is called a double spend. If an attacker is able to change the ordering of events, they could change who or where they sent money. They could send the equivalent of $5 to one person and send the same $5 to another person. Of course this is a problem that only exists in the digital world — people can’t give the same $5 bill (cash) to two people. In the digital world, this type of action is prevented by trusted third parties like banks. In blockchain, there is no third party to prevent this from occurring, because it’s the job of the consensus protocol.

Attacking the network could be a positive outcome for a player for a few reasons. First, they could double spend their money. Second, they could take advantage of the disarray caused by the network security breach by betting against the currency of that blockchain (shorting). And third, they could bring down a network for other reasons such as competition between blockchains or to bring more power back to central authorities like governments.

Throughout the following research regarding Proof of Work and Proof of Stake, the players will be weighing the tradeoffs of being rewarded for honesty and the rewards for being dishonest and attacking the network.

PROOF OF WORK

The first consensus protocol created is called Proof of Work. Originally created by Adam Back for Hashcash, Proof of Work was later used for the first blockchain, Bitcoin. Satoshi Nakomoto is the pseudonym of the creator of Bitcoin. Satoshi wrote the white paper in 2008 and created the first Bitcoin block in 2009. Since Bitcoin is the first and most widely-used Proof-of-Work blockchain, as well as having the largest market capitalization, in the following analysis I will use Bitcoin and Proof of Work interchangeably.

In a nutshell, Proof of Work consists of trusting the chain of blocks that has expended the most amount of energy to be created. In other words from Satoshi, “the longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power” (Nakamoto 2008). The creators of blocks that are expending energy are called miners. Miners use computing power to solve a cryptographic puzzle which is similar to a complex guessing game.

The amount of computational power the miner expends is directly proportional to the likelihood of solving the puzzle and “winning the block”. When the miner wins the block and only if they add the block to the longest chain, they receive a reward. That reward is newly created Bitcoin and all of the transaction fees associated with the transactions within the block. Here is a simplified diagram of the path of a transaction on the Bitcoin network. For the next step further in understanding, there are two recommended videos at the end of the paper.

As a reminder, the computational power expended by miners is directly proportional to the probability of winning the next block. If a miner or group of miners takes over 51% of the computing power, they may attempt to attack. There are many misconceptions around 51% attacks that are important to dispel before looking at the game theory of an attack. The most important misconception is that a miner or group of miners attempting a 51% attack can change all of the transactions in the blockchain. In reality, miners can only change the ordering of transactions that they are directly tied to through their personal cryptographic keys. If an attack occurs, a bystander disconnected from the attacker won’t lose their Bitcoin. The next misconception is that the attack will immediately allow the attacker to double spend and change the ordering of the blockchain. In order to understand why this is a misconception, the below scenario shows why it’s not so simple.

The left side depicts five miners or groups of miners that each own 20% of the computational power for Bitcoin mining. One of the miners wins the block and then adds it to the chain of blocks. On the right side, Rob has included a transaction of one Bitcoin sent to Porsche in the second block so he can buy his new car. The most important learning point of 51% attacks is that participants wait for blocks to be stacked on top of the block with their transaction before they consider that transaction secured. For most participants, waiting six blocks or approximately one hour is enough to ensure the transaction is final. For larger transactions, the receiving entity could require longer waiting time and the opposite could apply for smaller transactions.

For this example, Porsche is waiting six blocks so they will give Rob his Porsche after the eighth block is added to the blockchain. What many people believe about attacks is that if Rob controls 51% of the network, he will be able to fork or create a new chain that will trick Porsche. See below for a depiction of this concept.

The diagram on the left shows that Rob has taken over three of the miners and now owns 60% of the network. He starts a new chain where he sends the same Bitcoin that he sent to Porsche to his friend instead. He is attempting to double spend. Since he has the majority of the network, his attacking chain begins to outpace the original chain.

On the right, it becomes clear why this idea of an attack isn’t valid. As soon as Rob’s attacking chain is longer than the original chain, all miners will be incentivized to add to that chain and therefore it will become the trusted chain. When that happens, the transaction that Rob sent to Porsche will become invalid and Porsche won’t give Rob his car. Now that it’s more clear what an attack doesn’t consist of, the following diagrams will describe the dynamics of a potentially successful attack.

Rob is now waiting to begin the attack until Porsche has given him the car. Now that the eight block has been mined, Porsche has trusted the transaction and let Rob drive off the lot. Rob takes over 60% of the network and begins the attack. In order to successfully send the same Bitcoin to his friend, Rob will have to catch up to the longest chain. Based on the percentage of mining power that Rob owns (60%), he will win three blocks out of every five blocks so it will take approximately thirty blocks or five hours to catch the main chain.

In order to attain 60% of the network today, Rob would have to purchase $30B in mining equipment. That actually seems like an attainable number for a nearly $1T asset. But the mining equipment isn’t freely available and natural supply chain limitations will make purchasing this quantity very difficult. As the planning attacker seeks to buy more and more mining equipment, the price will be driven up. It’s important to note that the mining equipment isn’t any normal computer. Bitcoin uses Application Specific Integrated Circuits or ASIC for mining. Their only purpose is to mine Bitcoin. For this reason, an attack against the network would destroy the remaining value of the ASICS which further complicates the cost and benefits of an attack.

The next financial aspect to understand is the cost of the electricity to pull off Rob’s attack. For a five hour attack with 60% of the network today, the electricity cost would be somewhere around $5–10M. The opportunity cost of not mining blocks for the longest chain and foregoing the block rewards would be in the range of $4–6M at current prices in Sept 2021.

Another consideration is the waiting time before accepting a transaction is valid. Waiting for blocks or confirmations to be added to the chain before accepting a transaction makes the attack difficult to assess for an attacker. Typically larger transactions will wait for more confirmations, so the cost of an attack will increase as the benefit of a double spend increases. Now that the dynamics of an attack are more clear, the game theory analysis begins.

To set up the baseline payoff matrix for an attack, let us first start by understanding the players. For this game, there will be two players that each have 26% of the network’s computing power. Therefore, if they combine together they have more than 50% of the network and can attack. The next step is to analyze the payoffs. In the top left, both miners continue honest mining and both receive their portion of the blocks and rewards going forward. In the top right and bottom left, one player is attacking while the other player is remaining honest. The attacking player is wasting computational power and therefore receives the payoff of -1. The honest miner in this scenario continues to win blocks and receives 1 for a payoff.

This game is established with a pessimistic approach for the security of the network and assumes that the payoff for an attack is the best outcome for a player with 26%. The Bitcoin network has proven to be secure, but there may be reason to believe that the payoff for a successful attack in the future could become the optimal payoff. It’s likely that for this to be the highest payoff, returning both players with the payoff of 2, the miners would have to successfully double spend a large amount while also shorting the coin and making money off of the fall of the network. Another reason it could be the highest payoff is because a competitor or government will see the demise of the blockchain as the ultimate goal with no acceptable other endstate.

Now that the players and payoffs have been described, the next step is to look at game theoretical approaches for the players. First is to look at the Maximin strategy. How does each miner maximize the worst outcome? The maximin strategy is to always be honest because it ensures that the worst outcome is 1 instead of -1 when choosing to be dishonest and attack. Second is looking at the Nash equilibrium. For this game, there are two Nash equilibrium which means it doesn’t tell the whole story of how players will make their decision.

Therefore, the next step of analysis will help us understand how the players will think about the decision between the two Nash equilibrium. A helpful way to frame the question is as follows: “What do I need to believe about my opponent to make the right decision?”. To answer that, it is useful to consider mixed strategies, a game theoretical concept that involves probabilities

The above diagram with the equation shows all of the payoffs for the Alpha miner. The Alpha miner is trying to understand what she needs to believe about the Bravo miner to make the best decision. Therefore, she takes her payoffs for being honest and equates them to the payoffs for being dishonest. The result — when using these simplified payoffs — is that she has to believe that the Bravo miner is at least 33% likely to be honest to also choose to be honest. In other words, she has to believe that the Bravo miner is more than 67% likely to be dishonest for her to also be dishonest. Even with the pessimistic approach of maximum payoff (2) for a successful attack, the decision seems to be leaning towards honesty (and security).

After analyzing the complexity of an attack, one may believe the payoffs of an attack look different than the original construct of the payoff matrix. In the above payoff matrix, the payoffs for a winning attack are labeled as “W” and the payoff for a losing attack is a “L”. Then the Alpha miner is able to run a sensitivity analysis on the probabilities that she has to rely on regarding her opposing player.

Due to the heavy costs associated with an attack and the limited benefits, she may believe that “W” is not a 2 and instead a 1.5 or 1. If the successful attack is a 1.5, she only has to believe that there is a 20% chance that Bravo is an honest player in order to also be honest. If the successful attack payoff is 1 or equivalent to the reward for honest mining, then honest mining is the optimal strategy regardless of what she thinks about Bravo.

This payoff sensitivity table also weighs the changes to probabilities when she thinks that the failed attack payoff may not be as bad as expected. As the failed attack becomes less painful, Alpha’s risks are reduced and the likelihood to choose to attack increases although are never above 50% because the costs can never be zero due to the energy required to conduct an attack.

Based on this game theoretical analysis on Proof of Work using simplified payoffs, it’s understandable why the Bitcoin network is known for its security. Due to the incentive structure and energy requirement built into the consensus protocol, a successful attack is highly unlikely. To further complicate the situation for those that wish to attack, today it takes four mining groups or pools to join together to reach 50%.

As the number of players required to cooperate increases, the likelihood of a successful attack decreases. Coordinating across four entities and working to maximize return by attacking while shorting seems like an exciting scenario. But what if one player backs out and that player actually bets on the price going up (long position)? That player will win a greater portion of the rewards while the others waste energy and the attackers’ short position may turn into a terrible investment. It’s clear that decentralization of mining is an important goal for the Bitcoin network as participants hope to increase security.

https://btc.com/btc/insights-pools

One of the counterarguments to the long term security of Bitcoin is related to the incentives for mining. The number of new Bitcoins that are rewarded to miners decreases by half every four years until the total number of Bitcoin (21 Million) have been mined. As the newly minted coin reward decreases, the payoff for being honest decreases. The fact that the reward for honesty remains the same regardless of the decision of the opponent, the payoff for honesty is less significant in the analysis than the payoffs for winning or losing an attack. Whether the payoff for honesty is 1, 0.5, or 0.25, Alpha still has to believe that Bravo is 33% likely to be honest to also be honest.

The payoff for a failed attack may decrease as the reward for honest mining decreases. The change in the cost of mining equipment (ASICs) and the cost of electricity is unknown long term, so this analysis won’t speculate on those costs. The variable that is more estimable is the opportunity cost of not receiving the reward for honestly mining for blocks. As the reward decreases, the opportunity cost of a failed attack will also decrease. The price of Bitcoin may increase which could increase the opportunity cost, but that would also increase the benefit of the attack (higher price means the fraud is more lucrative). Transaction fees could grow significantly which would also increase the opportunity cost and promote stronger security, but would also mean a different paradigm for the experience of using the Bitcoin blockchain for storing and transferring value (high fees). The payoff sensitivity table displayed earlier in the paper is a great way to test hypotheses during different scenarios including the diminishing Bitcoin reward. More detailed analysis of the impact of halving is beyond the scope of this paper.

Another counterargument is that a government or competitor may not be incentivized by the rewards in the system. The game theory analysis still applies to those players. A government or competitor will have different characteristics of payoffs. For example, a government may not be as worried about the cost of an attack when their goal is to eliminate Bitcoin literally at any cost. But the government will have different risks to account for — like if they fail the attack, the confidence in the network will increase and put them in a worse position than if they had not attacked in the first place. The same goes for a competitor.

A complicating factor for a government attack is the mining distribution across countries. The below map is the mining distribution across the globe as of March 2021 according to the University of Cambridge Bitcoin Electricity Consumption Index. Two months after this map was created, China cracked down on mining and essentially all Bitcoin miners have been migrating out of China to other countries. If China didn’t coordinate an attack when they had 46% in March 2021 or when they had 75% in September 2019, the chance of a future attack from China or any other country seems to be rapidly in decline.

https://cbeci.org/mining_map

https://www.jbs.cam.ac.uk/insight/2021/new-data-reveals-timeline-of-chinas-bitcoin-mining-exodus/

The complexity of the game and the different characteristics of players are important factors when thinking about the probability of a successful attack. This analysis simplified the game by including only two players and only using a range of -1 to 2 for the payoffs. It is not an all encompassing answer to the future security of Bitcoin, but it’s a guideline for how players will make decisions in the game of mining Bitcoin. This research suggests that the incentive structure and requirement of energy built into the Proof of Work consensus protocol and the complexity of coordination across entities and countries make a 51% attack highly unlikely.

PROOF OF STAKE

The first Bitcoin was mined in 2009, thus starting the new technology of blockchain. Since its inception there has always been an argument that Bitcoin uses too much energy. As of September 2021, Bitcoin uses approximately 100 Terawatt Hours Per Year which is comparable to the energy draw of smaller countries (University of Cambridge 2021).

https://cbeci.org/cbeci/comparisons

“The “one-sentence philosophy” of proof of stake is thus not “security comes from burning energy”, but rather “security comes from putting up economic value-at-loss” (Buterin 2016). Instead of Miners using the physical resource of energy to secure the blockchain, Proof of Stake has Validators that use a “synthetic resource” to secure the blockchain by “staking” or committing their coins on the network (Hoskinson 2021). The probability of winning a block is decided by the proportion of stake that the validator has instead of the amount of computing power it is committing to the network. See below for a basic overview of a Proof of Stake transaction.

The obvious benefit of requiring validators to stake their coins on the network is that an attack against the network would devalue the worth of their own coins. Bitcoin doesn’t have this benefit because miners aren’t required to own any Bitcoin. There are many intricacies to different versions of Proof of Stake, but the following analysis will focus on the most basic attributes of the protocol. In the below scenario, there are five validators or five groups of validators that have equal proportions of the stake = 20% of the coins. Therefore, each validator has a 20% chance of winning the next block and receiving the block reward of new coins and transaction fees.

Now that the basics are more clear, the next step is to look at the different versions of attacks. This analysis will focus on two attacks — short range attacks and long range attacks. A short range attack is any attempt to create a new chain of blocks that doesn’t start at the original block in the chain. During a short range attack, an attacker is attempting to manipulate the ordering of transactions like an attacker in Proof of Work.

In order to successfully create the longest chain in Proof of Stake, the validators must take over more than 50% of the network. Taking over 50% of the network in Proof of Stake is very costly because as the attacker buys more coins the price will increase as supply decreases and demand increases. Of course the cost specifics will vary based on current prices and supply/demand of the Proof of Stake coin being used in the attack.

During this short range attack, Jess takes over 60% of the network and attempts to create a new chain. Proof of Stake protocols use an economic disincentive to prevent this type of attack, “there is a built-in “slashing” mechanism in the proof of stake consensus by which a large portion of the attacker’s stake (and no one else’s stake) can get automatically destroyed” (Buterin 2020). Players should already be wary of attacking because it will impact the value of the coins that they have staked. Slashing further punishes the attacker by destroying their coins and ending the attack as the attacker no longer has more than 50% of the staked coins.

The game theory behind short range attacks is rather simple as outlined below. The game is set up similar to the Proof of Work game — with two players each owning 26% of the probability to earn blocks. For short range attacks, slashing reduces any upside from a successful attack and the optimal outcome is always to continue honest validating. The Nash Equilibrium is when both are honest and the Maximin strategy is also to be honest.

The next version of an attack is called a Long Range attack that must start from the original block in the blockchain. In this scenario, Jess goes back to the original block and starts creating a new chain that she aims to make longer than the main chain. “To alter the history of the main chain, [Jess] must generate a higher number of minted blocks in parallel to the main-chain. However, she is bound by the fact that she has a fixed chance of producing blocks. To increase her chances of competing with the main-chain, she would need to be able to forge the blocks of another validator as well.” (Deirmentzoglou 2019).

In the below diagram, the situation is that Jess owned 40% of the staked coins at the beginning of the chain and Rob owned 20% of the coins. Therefore, Jess has to convince Rob to join the attack so she can also forge his blocks. Convincing Rob could be difficult and require bribery or Rob may not be involved in the network any longer and may join the attack without any bribery necessary.

If Jess and Rob are able to outpace the main chain, their blocks and transactions that they placed in their blocks would technically be the longest and most trusted chain. But will the chain be trusted? After working on the main chain for days, months or even years, will the validators in the network simply move on and accept the change?

Behind all of these validating computers are humans. It’s unlikely that they would accept the new chain. It’s more likely that they would work together to ensure the new chain isn’t accepted and instead continue working on the original chain. “Thus such an attack would be detected, recognized as an attack, and the new history rejected. If this is implemented correctly, there is no problem with this, except that it changes the trust model from that of Bitcoin. 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 vulnerable to legal pressure, attacks on “trusted” entities, and network attacks” (Poelstra 2015).

The idea of accepting this different version of consensus outside the protocol is contentious as Poelstra outlines. To reduce the ability for a long range attack to occur in the first place, leaders and developers in the Proof of Stake communities have developed several countermeasures. Three of those countermeasures are “moving checkpoints”, “key-evolving cryptography”, and the “Plenitude Rule” (Deirmentzoglou 2019).

“The idea behind moving checkpoints is that there is a quota on the latest n number of blocks of the chain which can be reorganised” (Deirmentzoglou 2019). Although this does remove the ability to start from the genesis block, it requires all validators to now trust the checkpoint instead of the genesis block. Therefore the attack could start from the checkpoint and have the same fundamentals as a long range attack although the number of blocks to manipulate would be reduced. Key evolving cryptography changes the keys used by validators to create blocks after a certain number of blocks have been added on top of those blocks. For Jess and Rob, they would no longer be able to create the blocks at the beginning of the chain because they would no longer own the correct keys. For the attacker to move around this technological defense, it may be extremely complex and nearly impossible. The Plenitude Rule is used in the Ouroboros Genesis protocol for the Cardano blockchain. This countermeasure is rather complex and beyond the scope of this paper. Simplified, it uses the density of the chains to determine the trustworthiness of the chain. For Jess and Rob’s attack, they will only be able to validate 60% of the blocks from the beginning of the chain since validators are rotated as the chain is built. Since 40% of the blocks won’t be created, the attacking chain won’t be as “dense” and therefore won’t be trusted.

Taking into account all of the vulnerabilities and countermeasures, the game theory payoff matrix for Long Range Attacks looks very similar to that in Proof of Work. The primary difference is in the cost of a failed attack. Because no electricity is required, the losing attack isn’t as costly as Proof of Work. Several papers reference the idea of “costless simulation” for Proof of Stake, but there will always be a cost of time to coordinate and/or invent new ways around countermeasures. Also the attacker may have to pay to bribe other validators. Therefore, the attack isn’t costless and the payoff matrix labels the payoff for a failed attack as -0.5.

Again there are two Nash Equilibrium and the Maximin Strategy is to be honest. So the next step is to look at what each player needs to believe about each other to make the best decisions. This is where the difference between Proof of Work and Proof of Stake long range attacks becomes more clear. For the base case with the simplified payoff for a successful attack being 2 and a failed attack being -0.5, Alpha needs to believe that Bravo is at least 40% likely to be honest to also be honest. Or on the other hand, she needs to believe that Bravo is greater than 60% likely to be dishonest to also be dishonest.

This base case using simplified payoffs isn’t as optimistic as Proof of Work (33%), but the countermeasures may make the attack more costly or less beneficial which would bring down the payoff of both successful and failed attacks. Moving to the left and up on the sensitivity table above shows that the right countermeasures could bring the likelihood of a successful attack to nearly zero.

Based on the game theoretical analysis of short range and long range attacks, it’s understandable why large Proof of Stake chains like Cardano, Algorand, Binance Chain, and Cosmos are known to be extremely secure. Before concluding, it’s important to look at the distribution of coins within a Proof of Stake network before making assumptions about security. Each chain has different rules about how much each validator can stake and there are issues identifying the owner of coins since one person could have several wallets of coins and/or several validating pools where they are staking their coins. One way to understand distribution is by looking at how the coins were distributed when the chain was originally created. Unlike Bitcoin where every Bitcoin was mined, Proof of Stake has to start with a coin distribution or Initial Coin Offering (ICO). Below is a diagram that compares how some of the top coins were distributed at their creation. This doesn’t mean that the coins are still distributed in this way.

https://medium.com/open-source-x/what-does-increased-insider-ownership-in-public-blockchains-mean-97f8e9e50368

The high percentage of “Insider” allocation for chains like Binance, Solana, and Avalanche seems to go against the decentralized nature of blockchains. “Public Sale” also isn’t perfect because there are people with more capital and/or privy information to the timing of the sale or where to buy the most at opening. Regardless of the way chains distribute their coins, there is a moment during ICO that will allow some players to accumulate large amounts of coins for an immediate or future attack. The distribution problem in Proof of Stake is further reinforced because those that stake the most coins have a higher probability of winning more coins and growing their portion of the stake. On the other hand, Proof of Stake avoids the economies of scale problem that may lead to centralization in Proof of Work. When purchasing ASICs, large Bitcoin mining companies may have more of an advantage in the market because they are able to buy in larger quantities at cheaper per unit cost. When a player in the Proof of Stake game tries to accumulate coins, they are required to buy on the same market as small players and any significant buying will raise prices.

Based on the game theoretical analysis of the Proof of Stake consensus protocol, there seems to be a very low probability of a successful 51% attack. Just like miner distribution for Bitcoin, coin distribution in Proof of Stake should also be assessed when gauging security risks.

CONCLUSION

Blockchains are distributed ledgers & maintaining consensus among all players is difficult but achievable. This analysis of the game theory behind the top two consensus protocols suggests that Proof of Work and Proof of Stake are reasonably safe from 51% attacks since three different game theory solution concepts point to “attack” not being an optimal strategy. Although both protocols can provide security, a key differentiator between the two is that long-range attacks in Proof of Stake don’t require the attacker to pay for a tangible world resource like Proof of Work.

An important consideration in the relative safety of both protocols is how concentrated the distribution of mining or stake is, since the analysis suggests that an attack may only be optimal when it involves coordination among a small number of players combining for majority control. For Bitcoin, the current distribution requires four or more groups of miners to combine forces to successfully 51% attack which would increase the complexity and further reduce the likelihood of an attack. For Proof of Stake coins, it’s important to analyze the blockchain’s coin and stake distribution before using the chain or storing wealth on the chain. As the distribution widens and more players need to coordinate in an attack, the greater one can trust the security of the chain.

There are several different ways to analyze each protocol ranging from their impact on the environment to their ability to scale and support different use cases. Nothing in this paper should be taken as investment advice or interpreted as definitive support of one protocol over another. With the goal of continuing my learning, I welcome any feedback that may help improve my analysis.

REFERENCES

RECOMMENDED MEDIA

RECOMMENDED READINGS


Blockchain Consensus Protocols & Game Theory was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.